//
// Created by Lantz on 2024/6/9.
//

/**
 * 试用贪心算法求解汽车加油问题：算法求解汽车加油问题：
 * 已知一辆汽车加满油后可行驶n公里。现想从a地驶到b地，
 * 而旅途中有k个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。
 */

#include <iostream>
#include <bits/stdc++.h>
const int maxn = 10;

using namespace std;

/**
 * @param n 汽车油量
 * @param k 数组长度
 * @param s 加油站数组
 */
void Greedy(int n, int k, int s[]){

    for (int i = 0; i <= k; ++i) {
        if(s[i] > n){
            cout<<"汽车达不到下一个加油站"<<endl;
            return;
        }
    }

    int sum = 0; // 能走多远
    int count = 0; // 需要加多少次油
    cout<<"需要加油的加油站："<<endl;
    for (int i = 0; i <= k; ++i) {
        sum += s[i];
        if(sum > n){
            count++;
            sum = s[i];
            cout<<i<<" ";
        }
    }
    cout<<endl;
    cout<<"需要加油的次数:"<<endl;
    cout<<count;
}

int main(){
    int n, k;
    int s[maxn];

    cout << "请输入汽车满油可行驶的距离和旅途中加油站的个数：" << endl;
    cin >> n >> k;
    cout << "请依次输入各个加油站之间的距离：" << endl;
    for (int i = 0; i <= k; i++)
        cin >> s[i];
    Greedy(n, k, s);
    
    return 0;
}